package com.lsa.iview.trees;

import static com.lsa.iview.trees.BinaryTreeUtils.createTree;
import static com.lsa.iview.trees.BinaryTreeUtils.inorder;
import static com.lsa.iview.trees.BinaryTreeUtils.inorderIter;
import static com.lsa.iview.trees.BinaryTreeUtils.postorder;
import static com.lsa.iview.trees.BinaryTreeUtils.postorderIter;
import static com.lsa.iview.trees.BinaryTreeUtils.preorder;
import static com.lsa.iview.trees.BinaryTreeUtils.preorderIter;
import static com.lsa.iview.trees.BinaryTreeUtils.writeAsTgfToFile;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

import junit.framework.TestCase;

import org.apache.commons.io.FileUtils;
import org.junit.Assert;

import com.google.common.collect.Lists;
import com.lsa.helpers.ISimpleClosure;
import com.lsa.helpers.IntegerComparator;
import com.lsa.helpers.Utils;
import com.lsa.iview.lists.SingeLinkedList;
import com.lsa.iview.trees.BinaryTree.Node;
import com.lsa.iview.trees.BinaryTreeUtils.NodeWithLevel;
import com.lsa.iview.trees.BinaryTreeUtils.WithNextRight;


public class TestBinaryTree extends TestCase {
	public void testSimple() throws IOException {
		BinaryTree<Integer> t = createTree(IntegerComparator.instance(), 2, 1, 5);
		File path = writeAsTgfToFile(t, "data/gen/iview/trees/testSimple1.tgf");
		Assert.assertEquals(FileUtils.readFileToString(new File("data/iview/trees/testSimple1.tgf")), FileUtils.readFileToString(path));
		
		t = createTree(IntegerComparator.instance(), 5, 1, 6, 4, 2, 3);
		path = writeAsTgfToFile(t, "data/gen/iview/trees/testSimple2.tgf");
		Assert.assertEquals(FileUtils.readFileToString(new File("data/iview/trees/testSimple2.tgf")), FileUtils.readFileToString(path));
		
		t = createTree(IntegerComparator.instance(), 1, 2, 3, 4, 5, 6);
		path = writeAsTgfToFile(t, "data/gen/iview/trees/testSimple3.tgf");
		Assert.assertEquals(FileUtils.readFileToString(new File("data/iview/trees/testSimple3.tgf")), FileUtils.readFileToString(path));
		
		t = createTree(IntegerComparator.instance(), 5, 4, 3, 2, 1);
		path = writeAsTgfToFile(t, "data/gen/iview/trees/testSimple4.tgf");
		Assert.assertEquals(FileUtils.readFileToString(new File("data/iview/trees/testSimple4.tgf")), FileUtils.readFileToString(path));
		
		t = createTree(IntegerComparator.instance(), 5, 1, 6, 4, 2, 3, 17, 11, 8, 9);
		path = writeAsTgfToFile(t, "data/gen/iview/trees/testSimple5.tgf");
		Assert.assertEquals(FileUtils.readFileToString(new File("data/iview/trees/testSimple5.tgf")), FileUtils.readFileToString(path));
	}
	
	public void testLookup() throws IOException {
		BinaryTree<Integer> t1 = createTree(IntegerComparator.instance(), 1, 2, 3, 4, 5, 6);
		BinaryTree<Integer> t2 = createTree(IntegerComparator.instance(), 5, 1, 6, 4, 2, 3);
		for (int i = 1; i < 7; i++) {
			Assert.assertTrue(t1.lookupNode(i).getData() == i);
			Assert.assertTrue(t2.lookupNode(i).getData() == i);
		}
	}
	
	public void testInorder() {
		BinaryTree<Integer>  t2 = createTree(IntegerComparator.instance(), 5, 1, 6, 4, 2, 3);
		List<Integer> traversal = new ArrayList<>();
		inorder(t2.getRoot(), traversal);
		
		List<Integer> expectedTraversal = Arrays.asList(1, 2, 3, 4, 5, 6);
		Assert.assertEquals(traversal, expectedTraversal);
		
		List<Integer> iteratedTraversal = new ArrayList<>();
		inorderIter(t2.getRoot(), iteratedTraversal);
		Assert.assertEquals(traversal, iteratedTraversal);
		
		t2 = createTree(IntegerComparator.instance(), 5, 1, 6, 4, 2, 3, 17, 11, 8, 9);
		
		inorder(t2.getRoot(), traversal);
		
		inorderIter(t2.getRoot(), iteratedTraversal);
		Assert.assertEquals(traversal, iteratedTraversal);
	}
	
	public void testPreorder() {
		BinaryTree<Integer>  t2 = createTree(IntegerComparator.instance(), 5, 1, 6, 4, 2, 3);
		List<Integer> traversal = new ArrayList<>();
		preorder(t2.getRoot(), traversal);
		
		List<Integer> expectedTraversal = Arrays.asList(5, 1, 4, 2, 3, 6);
		Assert.assertEquals(traversal, expectedTraversal);
		
		List<Integer> iteratedTraversal = new ArrayList<>();
		preorderIter(t2.getRoot(), iteratedTraversal);
		Assert.assertEquals(traversal, iteratedTraversal);
		
		t2 = createTree(IntegerComparator.instance(), 5, 1, 6, 4, 2, 3, 17, 11, 8, 9);
		traversal = new ArrayList<>();
		preorder(t2.getRoot(), traversal);
		
		iteratedTraversal = new ArrayList<>();
		preorderIter(t2.getRoot(), iteratedTraversal);
		Assert.assertEquals(traversal, iteratedTraversal);
	}
	
	public void testPostorder() {
		BinaryTree<Integer>  t2 = createTree(IntegerComparator.instance(), 5, 1, 6, 4, 2, 3);
		List<Integer> traversal = new ArrayList<>();
		postorder(t2.getRoot(), traversal);
		
		List<Integer> expectedTraversal = Arrays.asList(3, 2, 4, 1, 6, 5);
		Assert.assertEquals(traversal, expectedTraversal);
		
		List<Integer> iteratedTraversal = new ArrayList<>();
		postorderIter(t2.getRoot(), iteratedTraversal);
		Assert.assertEquals(traversal, iteratedTraversal);
		
		t2 = createTree(IntegerComparator.instance(), 5, 1, 6, 4, 2, 3, 17, 11, 8, 9);
		traversal = new ArrayList<>();
		postorder(t2.getRoot(), traversal);
		
		iteratedTraversal = new ArrayList<>();
		postorderIter(t2.getRoot(), iteratedTraversal);
		Assert.assertEquals(traversal, iteratedTraversal);
	}
	
	public void testMaxDepth() {
		BinaryTree<Integer> t = createTree(IntegerComparator.instance(), 1, 2, 3, 4, 5);
		Assert.assertEquals(5, BinaryTreeUtils.maxDepth(t));
		
		t = createTree(IntegerComparator.instance(), 1);
		Assert.assertEquals(1, BinaryTreeUtils.maxDepth(t));
		
		t = createTree(IntegerComparator.instance(), 5, 1, 6, 4, 2, 3, 17, 11, 8, 9);
		Assert.assertEquals(6, BinaryTreeUtils.maxDepth(t));
		
		t = createTree(IntegerComparator.instance(), 2, 1, 3);
		Assert.assertEquals(2, BinaryTreeUtils.maxDepth(t));
		
		t = createTree(IntegerComparator.instance(), 5, 1, 6, 4, 2, 3);
		Assert.assertEquals(5, BinaryTreeUtils.maxDepth(t));
		
		t = createTree(IntegerComparator.instance(), 20, 107, 33, 38, 48, 70,
				136, 112, 109, 130, 116, 245, 138, 228, 183, 201, 231, 233,
				265, 295);
		Assert.assertEquals(8, BinaryTreeUtils.maxDepth(t));
	}
	
	public void testMin() {
		List<Integer> l = Arrays.asList(20, 107, 33, 38, 48, 70,
				136, 112, 109, 130, 116, 245, 138, 228, 183, 201, 231, 233,
				265, 295);
		BinaryTree<Integer> t = createTree(IntegerComparator.instance(), l.toArray(new Integer[0]));
		Assert.assertEquals(Collections.min(l), BinaryTreeUtils.minValue(t));
		
		l = Arrays.asList(1);
		t = createTree(IntegerComparator.instance(), l.toArray(new Integer[0]));
		Assert.assertEquals(Collections.min(l), BinaryTreeUtils.minValue(t));
		
		l = Arrays.asList(2, 1, 3);
		t = createTree(IntegerComparator.instance(), l.toArray(new Integer[0]));
		Assert.assertEquals(Collections.min(l), BinaryTreeUtils.minValue(t));
	}
	
	public void testRootToLeafSum() {
		BinaryTree<Integer> t = createTree(IntegerComparator.instance(), 5, 4,
				11, 7, 2, 8, 13, 4, 1);
		
		Assert.assertEquals(true, BinaryTreeUtils.hasRootToLeafSum(t, 12));
		Assert.assertEquals(true, BinaryTreeUtils.hasRootToLeafSum(t, 15));
		Assert.assertEquals(true, BinaryTreeUtils.hasRootToLeafSum(t, 31));
		Assert.assertEquals(true, BinaryTreeUtils.hasRootToLeafSum(t, 29));
		Assert.assertEquals(false, BinaryTreeUtils.hasRootToLeafSum(t, 6));
		Assert.assertEquals(false, BinaryTreeUtils.hasRootToLeafSum(t, 0));
		
	}
	
	public void testEnumerateRootToLeafPathes() {
		/*5,4,2,1
5,4,2,4
5,11,7,8
5,11,13*/
		BinaryTree<Integer> t = createTree(IntegerComparator.instance(), 5, 4,
				11, 7, 2, 8, 13, 4, 1);
		List<List<Integer>> expectedLists = Arrays.asList(Arrays.asList(5, 4, 2, 1),
				Arrays.asList(5, 4, 2, 4), Arrays.asList(5, 11, 7, 8),
				Arrays.asList(5, 11, 13));
		final List<List<Integer>> actualLists = new ArrayList<>();
		BinaryTreeUtils.enumerateRootToLeafPathes(t.getRoot(), new ISimpleClosure<LinkedList<Node<Integer>>>() {
			@Override
			public Void invoke(LinkedList<Node<Integer>> l) throws RuntimeException {
				actualLists.add(toIntList(l));
				return null;
			}
			
			private List<Integer> toIntList(List<Node<Integer>> l) {
				List<Integer> rl = new ArrayList<>();
				for (Node<Integer> n : l) {
					rl.add(n.getData());
				}
				return rl;
			}
		});
		Assert.assertEquals(expectedLists, actualLists);
	}
	
	public void testMirror() {
		BinaryTree<Integer> t = createTree(IntegerComparator.instance(), 5, 4,
				11, 7, 2, 8, 13, 4, 1);
		List<Integer> traversal = new ArrayList<>();
		BinaryTreeUtils.inorder(t.getRoot(), traversal);
		List<Integer> mirrorTraversal = new ArrayList<>();
		BinaryTreeUtils.mirror(t.getRoot());
		BinaryTreeUtils.inorder(t.getRoot(), mirrorTraversal);
		Collections.reverse(traversal);
		Assert.assertEquals(traversal, mirrorTraversal);
	}
	
	public void testIsSame() {
		List<Integer> l = Arrays.asList(20, 107, 33, 38, 48, 70,
				136, 112, 109, 130, 116, 245, 138, 228, 183, 201, 231, 233,
				265, 295);
		BinaryTree<Integer> t1 = createTree(IntegerComparator.instance(), l.toArray(new Integer[0]));
		BinaryTree<Integer> t2 = createTree(IntegerComparator.instance(), l.toArray(new Integer[0]));
		Assert.assertEquals(true, BinaryTreeUtils.isSame(IntegerComparator.instance(), t1.getRoot(), t2.getRoot()));
		
		l = Arrays.asList(20, 107, 33, 38, 48, 70,
				136, 112, 109, 130, 116, 245, 138, 228, 183, 201, 231, 233,
				265, 295);//                                           |||
		List<Integer> l2 = Arrays.asList(20, 107, 33, 38, 48,//        ||| 
				70,//                                                  |||
				136, 112, 109, 130, 116, 245, 138, 228, 183, 201, 231, 234,
				265, 295);
		t1 = createTree(IntegerComparator.instance(), l.toArray(new Integer[0]));
		t2 = createTree(IntegerComparator.instance(), l2.toArray(new Integer[0]));
		Assert.assertEquals(false, BinaryTreeUtils.isSame(IntegerComparator.instance(), t1.getRoot(), t2.getRoot()));
		Assert.assertEquals(false, BinaryTreeUtils.isSame(IntegerComparator.instance(), t2.getRoot(), t1.getRoot()));
		
		l = Arrays.asList(20, 107, 33, 38, 48, 70,
				136, 112, 109, 130, 116, 245, 138, 228, 183, 201, 231, 233,
				265, 295);//                                           
		l2 = Arrays.asList(20, 107, 33, 38, 48,//         
				70,//                                                  
				136, 112, 109, 130, 116, 245, 138, 228, 183, 201, 231, 233,
				265);
		t1 = createTree(IntegerComparator.instance(), l.toArray(new Integer[0]));
		t2 = createTree(IntegerComparator.instance(), l2.toArray(new Integer[0]));
		Assert.assertEquals(false, BinaryTreeUtils.isSame(IntegerComparator.instance(), t1.getRoot(), t2.getRoot()));
		Assert.assertEquals(false, BinaryTreeUtils.isSame(IntegerComparator.instance(), t2.getRoot(), t1.getRoot()));
		
	}
	
	public void testCountTrees(){
		int[] catalan = new int[]{1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796};
		for (int i = 1; i <= catalan.length; i++) {
			Assert.assertEquals(catalan[i-1], BinaryTreeUtils.countTrees(i));
		}
	}
	
	public void testIsBst() {
		List<Integer> l = Arrays.asList(20, 107, 33, 38, 48, 70,
				136, 112, 109, 130, 116, 245, 138, 228, 183, 201, 231, 233,
				265, 295);
		BinaryTree<Integer> t = createTree(IntegerComparator.instance(), l.toArray(new Integer[0]));
		Assert.assertEquals(true, BinaryTreeUtils.isBst(IntegerComparator.instance(), t.getRoot(), -1, 1000));
		
		t.getRoot().getRight().getLeft().getRight().getRight().getRight().setData(1500);
		Assert.assertEquals(false, BinaryTreeUtils.isBst(IntegerComparator.instance(), t.getRoot(), -1, 1000));
		
		t = createTree(IntegerComparator.instance(), 1, 2, 3, 4, 5, 6);
		t.getRoot().getRight().getRight().getRight().setData(2);
		Assert.assertEquals(false, BinaryTreeUtils.isBst(IntegerComparator.instance(), t.getRoot(), -1, 1000));
		
		t = createTree(IntegerComparator.instance(), 5, 1, 6, 4, 2, 3, 17, 11, 8, 9);
		t.getRoot().getRight().getRight().getLeft().getLeft().setData(17);
		Assert.assertEquals(false, BinaryTreeUtils.isBst(IntegerComparator.instance(), t.getRoot(), -1, 1000));
	}
	
	public void testReadWritePreorder() throws IOException {
		testReadWritePreorder(1,2,3);
		testReadWritePreorder(3,2,1);
		testReadWritePreorder(3,2);
		testReadWritePreorder(2,3);
		testReadWritePreorder(1);
		testReadWritePreorder(5, 1, 6, 4, 2, 3, 17, 11, 8, 9);
		testReadWritePreorder(20, 107, 33, 38, 48, 70,
				136, 112, 109, 130, 116, 245, 138, 228, 183, 201, 231, 233,
				265, 295);
		testReadWritePreorder(4,2,1,3,6,5,7); // complete tree test
		
		testReadWritePreorder(1, 1);
		testReadWritePreorder(1, 1, 1);
		testReadWritePreorder(1, 1, 1, 1);
		testReadWritePreorder(1, 1, 1, 1, 1);
		testReadWritePreorder(20, 107, 33, 38, 48, 70,
				136, 112, 109, 130, 116, 116, 245, 138, 228, 183, 201, 201, 231, 233,
				265, 295);
		
		testReadWritePreorder(20, 107, 33, 38, 48, 70,
				136, 112, 109, 130, 116, 116, 245, 138, 228, 183, 201, 201, 231, 233,
				265, 295);
		testReadWritePreorder(2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2,
				2, 2, 2, 2, 2, 2, 85, 45, 38, 32, 24, 21, 10, 8, 3, 3, 3, 3, 3,
				3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 8, 7, 4, 4, 4, 4,
				4, 5, 5, 5, 5, 5, 5, 5, 7, 7, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7,
				7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
				8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10,
				10, 10, 10, 10, 10, 21, 11, 11, 11, 11, 11, 15, 14, 14, 13, 13,
				13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13,
				13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15,
				15, 15, 15, 15, 17, 17, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
				17, 17, 17, 17, 17, 17, 17, 17, 20, 20, 19, 19, 19, 18, 18, 18,
				18, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21,
				21, 21, 21, 21, 24, 22, 22, 22, 22, 22, 22, 22, 22, 22, 24, 23,
				23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 25, 25, 25,
				25, 25, 25, 25, 28, 27, 27, 27, 27, 27, 27, 26, 26, 26, 26, 26,
				26, 26, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28,
				28, 29, 29, 29, 29, 29, 29, 29, 29, 31, 31, 30, 30, 30, 30, 30,
				30, 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 32, 32,
				32, 32, 32, 32, 32, 36, 36, 36, 36, 34, 34, 33, 33, 33, 33, 33,
				33, 33, 33, 33, 33, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34,
				34, 36, 35, 35, 35, 35, 35, 35, 36, 36, 36, 36, 36, 36, 36, 36,
				38, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 38,
				38, 38, 38, 38, 38, 38, 38, 38, 38, 41, 39, 39, 39, 39, 39, 39,
				39, 39, 39, 39, 39, 40, 40, 40, 40, 40, 40, 40, 40, 41, 41, 41,
				41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 42, 42, 42, 42,
				42, 42, 42, 42, 42, 42, 42, 42, 42, 43, 43, 43, 43, 43, 43, 43,
				43, 43, 44, 44, 44, 44, 45, 45, 45, 45, 45, 68, 57, 55, 51, 49,
				49, 48, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 47, 47, 47,
				47, 47, 47, 47, 47, 48, 48, 48, 48, 48, 48, 49, 49, 49, 49, 49,
				49, 49, 51, 51, 51, 51, 51, 50, 50, 50, 50, 50, 50, 50, 50, 50,
				51, 51, 51, 51, 51, 51, 51, 51, 55, 52, 52, 52, 52, 52, 52, 52,
				52, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 55, 54,
				54, 54, 54, 54, 54, 54, 54, 55, 55, 55, 55, 55, 55, 55, 55, 55,
				55, 55, 55, 55, 57, 57, 56, 56, 56, 56, 56, 56, 56, 56, 56, 57,
				57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 59, 59, 59, 59, 59, 59,
				58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 59, 59, 59, 59,
				59, 59, 59, 59, 65, 65, 65, 65, 62, 61, 60, 60, 60, 60, 60, 60,
				60, 60, 61, 61, 61, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 64,
				64, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 64, 64, 64, 64, 64,
				64, 64, 64, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65,
				67, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 67, 67, 67,
				67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 68, 68, 68, 68, 68, 68,
				68, 82, 76, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69,
				73, 71, 71, 70, 70, 70, 70, 70, 70, 70, 70, 71, 71, 71, 71, 71,
				71, 71, 71, 71, 71, 72, 72, 72, 72, 72, 73, 73, 73, 73, 73, 76,
				76, 76, 74, 74, 74, 74, 74, 74, 74, 76, 76, 76, 75, 75, 75, 75,
				75, 75, 75, 76, 76, 76, 76, 76, 78, 78, 78, 78, 77, 77, 77, 77,
				77, 77, 77, 77, 78, 78, 78, 78, 78, 79, 79, 79, 79, 79, 79, 79,
				79, 79, 79, 79, 79, 79, 79, 79, 82, 80, 80, 80, 80, 80, 80, 80,
				80, 80, 80, 80, 80, 80, 80, 80, 81, 81, 81, 81, 81, 81, 81, 81,
				81, 81, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 84, 84, 83,
				83, 83, 83, 83, 83, 84, 84, 84, 84, 84, 84, 84, 84, 84, 85, 85,
				85, 85, 85, 85, 85, 85, 96, 93, 90, 86, 86, 86, 86, 86, 86, 86,
				86, 86, 88, 87, 87, 87, 87, 87, 87, 88, 88, 88, 88, 88, 88, 88,
				88, 88, 89, 89, 89, 89, 89, 89, 89, 89, 89, 89, 90, 90, 90, 90,
				90, 90, 90, 90, 90, 90, 92, 91, 91, 91, 92, 92, 92, 92, 92, 92,
				92, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93,
				95, 95, 95, 95, 95, 95, 94, 94, 94, 94, 94, 94, 94, 94, 95, 95,
				95, 95, 95, 95, 95, 95, 95, 95, 95, 95, 96, 96, 96, 96, 96, 96,
				96, 96, 98, 97, 97, 97, 97, 97, 97, 97, 98, 98, 98, 98, 98, 98,
				98, 98, 99, 99, 99, 99, 99, 99, 100, 100, 100, 100, 100, 100,
				100, 100, 100, 100);
	}

	private void testReadWritePreorder(Integer... arr) throws IOException,
			FileNotFoundException {
		BinaryTree<Integer> expected = createTree(IntegerComparator.instance(), arr);
		BinaryTreeUtils.writeBstInPreorder(expected.getRoot(), new File("data/gen/iview/trees/testPo.po"));
		BinaryTree<Integer> actual = BinaryTreeUtils.readIntegerBstFromPreorder(new File("data/gen/iview/trees/testPo.po"));
		writeAsTgfToFile(expected, "data/gen/iview/trees/testPoExpec.tgf");
		writeAsTgfToFile(actual, "data/gen/iview/trees/testPoAct.tgf");
		Assert.assertEquals(true, BinaryTreeUtils.isSame(IntegerComparator.instance(), expected.getRoot(), actual.getRoot()));
	}
	
	public void testCreateRandomTree() throws IOException {
		BinaryTree<Integer> t = BinaryTreeUtils.createRandomTree(1000, 1, 100);
		BinaryTreeUtils.writeBstInPreorder(t.getRoot(), new File("data/gen/iview/trees/testRandomTree.po"));
	}
	
	public void testSuccessorPredecessor() throws IOException {
		testSuccessorPredecessor(1, 2, 3, 4, 5, 6);
		testSuccessorPredecessor(1, 1);
		testSuccessorPredecessor(1);
		testSuccessorPredecessor(5, 1, 6, 4, 2, 3, 17, 11, 8, 9);
		testSuccessorPredecessor(1, 1, 2, 2, 3, 3, 4, 5, 5, 6);
		testSuccessorPredecessor(2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2,
				2, 2, 2, 2, 2, 2, 85, 45, 38, 32, 24, 21, 10, 8, 3, 3, 3, 3, 3,
				3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 8, 7, 4, 4, 4, 4,
				4, 5, 5, 5, 5, 5, 5, 5, 7, 7, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7,
				7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
				8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10,
				10, 10, 10, 10, 10, 21, 11, 11, 11, 11, 11, 15, 14, 14, 13, 13,
				13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13,
				13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15,
				15, 15, 15, 15, 17, 17, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
				17, 17, 17, 17, 17, 17, 17, 17, 20, 20, 19, 19, 19, 18, 18, 18,
				18, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21,
				21, 21, 21, 21, 24, 22, 22, 22, 22, 22, 22, 22, 22, 22, 24, 23,
				23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 25, 25, 25,
				25, 25, 25, 25, 28, 27, 27, 27, 27, 27, 27, 26, 26, 26, 26, 26,
				26, 26, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28,
				28, 29, 29, 29, 29, 29, 29, 29, 29, 31, 31, 30, 30, 30, 30, 30,
				30, 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 32, 32,
				32, 32, 32, 32, 32, 36, 36, 36, 36, 34, 34, 33, 33, 33, 33, 33,
				33, 33, 33, 33, 33, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34,
				34, 36, 35, 35, 35, 35, 35, 35, 36, 36, 36, 36, 36, 36, 36, 36,
				38, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 38,
				38, 38, 38, 38, 38, 38, 38, 38, 38, 41, 39, 39, 39, 39, 39, 39,
				39, 39, 39, 39, 39, 40, 40, 40, 40, 40, 40, 40, 40, 41, 41, 41,
				41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 42, 42, 42, 42,
				42, 42, 42, 42, 42, 42, 42, 42, 42, 43, 43, 43, 43, 43, 43, 43,
				43, 43, 44, 44, 44, 44, 45, 45, 45, 45, 45, 68, 57, 55, 51, 49,
				49, 48, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 47, 47, 47,
				47, 47, 47, 47, 47, 48, 48, 48, 48, 48, 48, 49, 49, 49, 49, 49,
				49, 49, 51, 51, 51, 51, 51, 50, 50, 50, 50, 50, 50, 50, 50, 50,
				51, 51, 51, 51, 51, 51, 51, 51, 55, 52, 52, 52, 52, 52, 52, 52,
				52, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 55, 54,
				54, 54, 54, 54, 54, 54, 54, 55, 55, 55, 55, 55, 55, 55, 55, 55,
				55, 55, 55, 55, 57, 57, 56, 56, 56, 56, 56, 56, 56, 56, 56, 57,
				57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 59, 59, 59, 59, 59, 59,
				58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 59, 59, 59, 59,
				59, 59, 59, 59, 65, 65, 65, 65, 62, 61, 60, 60, 60, 60, 60, 60,
				60, 60, 61, 61, 61, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 64,
				64, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 64, 64, 64, 64, 64,
				64, 64, 64, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65,
				67, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 67, 67, 67,
				67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 68, 68, 68, 68, 68, 68,
				68, 82, 76, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69,
				73, 71, 71, 70, 70, 70, 70, 70, 70, 70, 70, 71, 71, 71, 71, 71,
				71, 71, 71, 71, 71, 72, 72, 72, 72, 72, 73, 73, 73, 73, 73, 76,
				76, 76, 74, 74, 74, 74, 74, 74, 74, 76, 76, 76, 75, 75, 75, 75,
				75, 75, 75, 76, 76, 76, 76, 76, 78, 78, 78, 78, 77, 77, 77, 77,
				77, 77, 77, 77, 78, 78, 78, 78, 78, 79, 79, 79, 79, 79, 79, 79,
				79, 79, 79, 79, 79, 79, 79, 79, 82, 80, 80, 80, 80, 80, 80, 80,
				80, 80, 80, 80, 80, 80, 80, 80, 81, 81, 81, 81, 81, 81, 81, 81,
				81, 81, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 84, 84, 83,
				83, 83, 83, 83, 83, 84, 84, 84, 84, 84, 84, 84, 84, 84, 85, 85,
				85, 85, 85, 85, 85, 85, 96, 93, 90, 86, 86, 86, 86, 86, 86, 86,
				86, 86, 88, 87, 87, 87, 87, 87, 87, 88, 88, 88, 88, 88, 88, 88,
				88, 88, 89, 89, 89, 89, 89, 89, 89, 89, 89, 89, 90, 90, 90, 90,
				90, 90, 90, 90, 90, 90, 92, 91, 91, 91, 92, 92, 92, 92, 92, 92,
				92, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93,
				95, 95, 95, 95, 95, 95, 94, 94, 94, 94, 94, 94, 94, 94, 95, 95,
				95, 95, 95, 95, 95, 95, 95, 95, 95, 95, 96, 96, 96, 96, 96, 96,
				96, 96, 98, 97, 97, 97, 97, 97, 97, 97, 98, 98, 98, 98, 98, 98,
				98, 98, 99, 99, 99, 99, 99, 99, 100, 100, 100, 100, 100, 100,
				100, 100, 100, 100);
	}

	private void testSuccessorPredecessor(Integer... arr) throws IOException {
		List<Integer> l = Arrays.asList(arr);
		BinaryTree<Integer> t = createTree(IntegerComparator.instance(), arr);
		Collections.sort(l);
		Node<Integer> succNode = BinaryTreeUtils.min(t); // min
		Node<Integer> predNode = BinaryTreeUtils.max(t); // max
		for (int i = 1; i < l.size(); i++) {
			succNode = BinaryTreeUtils.successor(succNode);
			predNode = BinaryTreeUtils.predecessor(predNode);
			Assert.assertEquals((Integer)l.get(i), succNode.getData());
			Assert.assertEquals(l.get(l.size()-i-1), predNode.getData());
		}
	}
	
	public void testIterators() throws IOException {
		testIterators(1, 2, 3, 4, 5, 6);
		testIterators(1, 1);
		testIterators(1);
		testIterators(5, 1, 6, 4, 2, 3, 17, 11, 8, 9);
		testIterators(1, 1, 2, 2, 3, 3, 4, 5, 5, 6);
		testIterators(2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2,
				2, 2, 2, 2, 2, 2, 85, 45, 38, 32, 24, 21, 10, 8, 3, 3, 3, 3, 3,
				3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 8, 7, 4, 4, 4, 4,
				4, 5, 5, 5, 5, 5, 5, 5, 7, 7, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7,
				7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
				8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10,
				10, 10, 10, 10, 10, 21, 11, 11, 11, 11, 11, 15, 14, 14, 13, 13,
				13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13,
				13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15,
				15, 15, 15, 15, 17, 17, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
				17, 17, 17, 17, 17, 17, 17, 17, 20, 20, 19, 19, 19, 18, 18, 18,
				18, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21,
				21, 21, 21, 21, 24, 22, 22, 22, 22, 22, 22, 22, 22, 22, 24, 23,
				23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 25, 25, 25,
				25, 25, 25, 25, 28, 27, 27, 27, 27, 27, 27, 26, 26, 26, 26, 26,
				26, 26, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28,
				28, 29, 29, 29, 29, 29, 29, 29, 29, 31, 31, 30, 30, 30, 30, 30,
				30, 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 32, 32,
				32, 32, 32, 32, 32, 36, 36, 36, 36, 34, 34, 33, 33, 33, 33, 33,
				33, 33, 33, 33, 33, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34,
				34, 36, 35, 35, 35, 35, 35, 35, 36, 36, 36, 36, 36, 36, 36, 36,
				38, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 38,
				38, 38, 38, 38, 38, 38, 38, 38, 38, 41, 39, 39, 39, 39, 39, 39,
				39, 39, 39, 39, 39, 40, 40, 40, 40, 40, 40, 40, 40, 41, 41, 41,
				41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 42, 42, 42, 42,
				42, 42, 42, 42, 42, 42, 42, 42, 42, 43, 43, 43, 43, 43, 43, 43,
				43, 43, 44, 44, 44, 44, 45, 45, 45, 45, 45, 68, 57, 55, 51, 49,
				49, 48, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 47, 47, 47,
				47, 47, 47, 47, 47, 48, 48, 48, 48, 48, 48, 49, 49, 49, 49, 49,
				49, 49, 51, 51, 51, 51, 51, 50, 50, 50, 50, 50, 50, 50, 50, 50,
				51, 51, 51, 51, 51, 51, 51, 51, 55, 52, 52, 52, 52, 52, 52, 52,
				52, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 55, 54,
				54, 54, 54, 54, 54, 54, 54, 55, 55, 55, 55, 55, 55, 55, 55, 55,
				55, 55, 55, 55, 57, 57, 56, 56, 56, 56, 56, 56, 56, 56, 56, 57,
				57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 59, 59, 59, 59, 59, 59,
				58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 59, 59, 59, 59,
				59, 59, 59, 59, 65, 65, 65, 65, 62, 61, 60, 60, 60, 60, 60, 60,
				60, 60, 61, 61, 61, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 64,
				64, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 64, 64, 64, 64, 64,
				64, 64, 64, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65,
				67, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 67, 67, 67,
				67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 68, 68, 68, 68, 68, 68,
				68, 82, 76, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69,
				73, 71, 71, 70, 70, 70, 70, 70, 70, 70, 70, 71, 71, 71, 71, 71,
				71, 71, 71, 71, 71, 72, 72, 72, 72, 72, 73, 73, 73, 73, 73, 76,
				76, 76, 74, 74, 74, 74, 74, 74, 74, 76, 76, 76, 75, 75, 75, 75,
				75, 75, 75, 76, 76, 76, 76, 76, 78, 78, 78, 78, 77, 77, 77, 77,
				77, 77, 77, 77, 78, 78, 78, 78, 78, 79, 79, 79, 79, 79, 79, 79,
				79, 79, 79, 79, 79, 79, 79, 79, 82, 80, 80, 80, 80, 80, 80, 80,
				80, 80, 80, 80, 80, 80, 80, 80, 81, 81, 81, 81, 81, 81, 81, 81,
				81, 81, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 84, 84, 83,
				83, 83, 83, 83, 83, 84, 84, 84, 84, 84, 84, 84, 84, 84, 85, 85,
				85, 85, 85, 85, 85, 85, 96, 93, 90, 86, 86, 86, 86, 86, 86, 86,
				86, 86, 88, 87, 87, 87, 87, 87, 87, 88, 88, 88, 88, 88, 88, 88,
				88, 88, 89, 89, 89, 89, 89, 89, 89, 89, 89, 89, 90, 90, 90, 90,
				90, 90, 90, 90, 90, 90, 92, 91, 91, 91, 92, 92, 92, 92, 92, 92,
				92, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93, 93,
				95, 95, 95, 95, 95, 95, 94, 94, 94, 94, 94, 94, 94, 94, 95, 95,
				95, 95, 95, 95, 95, 95, 95, 95, 95, 95, 96, 96, 96, 96, 96, 96,
				96, 96, 98, 97, 97, 97, 97, 97, 97, 97, 98, 98, 98, 98, 98, 98,
				98, 98, 99, 99, 99, 99, 99, 99, 100, 100, 100, 100, 100, 100,
				100, 100, 100, 100);
	}
	
	public void testIterators(Integer... arr) throws IOException {
		List<Integer> list = Arrays.asList(arr);
		List<Integer> reversedList = Utils.reversedList(list);
		BinaryTree<Integer> tree = createTree(IntegerComparator.instance(), arr);
		Collections.sort(list); // reversedList is reverse sorted after this
		
		Iterator<Integer> listIter = list.iterator();
		Iterator<Integer> reversedListIter = reversedList.iterator();
		Iterator<Integer> treeIter = tree.iterator();
		Iterator<Integer> reverseTreeIter = BinaryTreeUtils.reverseIterator(BinaryTreeUtils.max(tree.getRoot()));
		
		while(listIter.hasNext()) {
			Assert.assertTrue(reversedListIter.hasNext());
			Assert.assertTrue(treeIter.hasNext());
			Assert.assertTrue(reverseTreeIter.hasNext());
			Assert.assertEquals(listIter.next(), treeIter.next());
			Assert.assertEquals(reversedListIter.next(), reverseTreeIter.next());
		}
	}
	
	public void testIntersection() throws IOException {
		testIntersection(array(), array(), array());
		testIntersection(array(1), array(1), array(1));
		testIntersection(array(1), array(1,2,3), array(1));
		testIntersection(array(), array(1,2,3), array());
		testIntersection(array(1,2,3),array(), array());
		testIntersection(array(2), array(1,2,3), array(2));
		testIntersection(array(1, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6, 10),
				array(-1, 2, 2, 3, 6, 6, 7, 7, 8, 8, 9), array(2, 2, 3, 6, 6));
		testIntersection(array(1,2,3), array(4,5), array());
		testIntersection(array(1,2,2), array(1,2,2), array(1,2,2));
		testIntersection(array(1,2,2,3), array(1,2,2,3), array(1,2,2,3));
		testIntersection(array(1,2,2,3), array(1,2,2), array(1,2,2));
		testIntersection(array(1, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6, 10),
				array(3, 3, 4, 4, 6, 6, 10, 11, 22, 32, 33),
				array(3, 3, 4, 4, 6, 6, 10));
		testIntersection(array(1, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6, 10,11,13,15),
				array(3, 3, 3, 4, 4, 6, 6, 7, 10, 12, 14, 15, 22, 32, 33),
				array(3, 3, 4, 4, 6, 6, 10, 15));
	}
	
	public void testIntersection(Integer[] arr1, Integer[] arr2, Integer[] expected) throws IOException {
		BinaryTree<Integer> t1 = createTree(IntegerComparator.instance(), arr1);
		BinaryTree<Integer> t2 = createTree(IntegerComparator.instance(), arr2);
		
		BinaryTree<Integer> intersection = BinaryTreeUtils.intersection(t1, t2);
		Assert.assertEquals(Arrays.asList(expected), Lists.newArrayList(intersection));  
	}
	
	public void testUnion() throws IOException {
		testUnion(array(), array(), array());
		testUnion(array(1), array(1), array(1));
		testUnion(array(1), array(1,2,3), array(1,2,3));
		testUnion(array(), array(1,2,3), array(1,2,3));
		testUnion(array(1,2,3),array(), array(1,2,3));
		testUnion(array(2), array(1,2,3), array(1,2,3));
		testUnion(array(1, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6, 10),
				array(-1, 2, 2, 3, 6, 6, 7, 7, 8, 8, 9), array(-1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6, 7, 7, 8, 8, 9, 10));
		testUnion(array(1, 2, 3), array(4, 5), array(1, 2, 3, 4, 5));
		testUnion(array(1, 2, 2), array(1, 2, 2), array(1, 2, 2));
		testUnion(array(1, 2, 2, 3), array(1, 2, 2, 3), array(1, 2, 2, 3));
		testUnion(array(1, 2, 2, 3), array(1, 2, 2), array(1, 2, 2, 3));
		testUnion(array(1, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6, 10),
				array(3, 3, 4, 4, 6, 6, 10, 11, 22, 32, 33),
				array(1, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6, 10, 11, 22, 32, 33));
		testUnion(array(1, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6, 10),
				array(3, 3, 4, 4, 6, 6, 6, 10, 11, 22, 32, 32, 33),
				array(1, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6, 6, 10, 11, 22, 32, 32, 33));
		testUnion(array(1, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6, 10, 11, 13, 15),
				array(3, 3, 3, 4, 4, 6, 6, 7, 10, 12, 14, 15, 22, 32, 33),
				array(1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 6, 6, 7, 10, 11, 12, 13,
						14, 15, 22, 32, 33));
	}
	
	public void testUnion(Integer[] arr1, Integer[] arr2, Integer[] expected) throws IOException {
		BinaryTree<Integer> t1 = createTree(IntegerComparator.instance(), arr1);
		BinaryTree<Integer> t2 = createTree(IntegerComparator.instance(), arr2);
		
		BinaryTree<Integer> union = BinaryTreeUtils.union(t1, t2);
		Assert.assertEquals(Arrays.asList(expected), Lists.newArrayList(union));  
	}
	
	public void testConnectNextRight() throws IOException {
//		BinaryTree<WithNextRight<Integer>> t = createCompleteTreeWithNextRight(10);
//		BinaryTree<WithNextRight<Integer>> t = createTreeWithNextRight(IntegerComparator.instance(), 1, 2, 4, 5, 8, 9, 16, 17, 18, 19, 10, 11, 20, 21, 22, 23, 3, 6, 7, 12, 13, 14, 15);
//		BinaryTree<WithNextRight<Integer>> t = createTreeWithNextRight(IntegerComparator.instance(), 4, 2, 6, 1, 3, 5, 7);
		
		BinaryTree<WithNextRight<Integer>> t = BinaryTreeUtils.createCompleteTreeWithNextRight(4);
		BinaryTreeUtils.connectNextRightRec(t.getRoot());
		List<Integer> siblings = new ArrayList<Integer>();
		exploreSiblings(t.getRoot(), siblings);
		Assert.assertEquals(Arrays.asList(7, 3, 11, 1, 5, 9, 13, 0, 2, 4, 6, 8, 10, 12, 14), siblings);
//		System.out.println(writeAsTgfToFile(t, "data/gen/iview/trees/test123.tgf").getAbsoluteFile());
	}
	
	public void testIterateLevels() {
		{
			BinaryTree<Integer> t = BinaryTreeUtils.createCompleteTree(5);
			testIterateLevels(Arrays.asList(Arrays.asList(15), Arrays.asList(7,
					23), Arrays.asList(3, 11, 19, 27), Arrays.asList(1, 5, 9, 13,
							17, 21, 25, 29), Arrays.asList(0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24,
									26, 28, 30)), 5, BinaryTreeUtils.iterateLevels(t.getRoot()));
		}
		
		{
			BinaryTree<Integer> t = createTree(IntegerComparator.instance(), 20, 107, 33, 38, 48, 70,
					136, 112, 109, 130, 116, 245, 138, 228, 183, 201, 231, 233,
					265, 295);
			testIterateLevels(Arrays.asList(Arrays.asList(20),
					Arrays.asList(107), Arrays.asList(33, 136),
					Arrays.asList(38, 112, 245),
					Arrays.asList(48, 109, 130, 138, 265),
					Arrays.asList(70, 116, 228, 295), Arrays.asList(183, 231),
					Arrays.asList(201, 233)), 8,
					BinaryTreeUtils.iterateLevels(t.getRoot()));
		}
	}
	
	public void testIterateLevelsZigzag() {
		{
			BinaryTree<Integer> t = BinaryTreeUtils.createCompleteTree(5);
			testIterateLevels(Arrays.asList(Arrays.asList(15), Utils.reversedList(Arrays.asList(7,
					23)), Arrays.asList(3, 11, 19, 27), Utils.reversedList(Arrays.asList(1, 5, 9, 13,
							17, 21, 25, 29)), Arrays.asList(0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24,
									26, 28, 30)), 5, BinaryTreeUtils.iterateLevelsZigzag(t.getRoot()));
		}
		
		{
			BinaryTree<Integer> t = createTree(IntegerComparator.instance(), 20, 107, 33, 38, 48, 70,
					136, 112, 109, 130, 116, 245, 138, 228, 183, 201, 231, 233,
					265, 295);
			testIterateLevels(Arrays.asList(Arrays.asList(20),
					Utils.reversedList(Arrays.asList(107)), Arrays.asList(33, 136),
					Utils.reversedList(Arrays.asList(38, 112, 245)),
					Arrays.asList(48, 109, 130, 138, 265),
					Utils.reversedList(Arrays.asList(70, 116, 228, 295)), Arrays.asList(183, 231),
					Utils.reversedList(Arrays.asList(201, 233))), 8,
					BinaryTreeUtils.iterateLevelsZigzag(t.getRoot()));
		}
	}
	
	private void testIterateLevels(List<List<Integer>> expected, int levelCount,  Iterable<NodeWithLevel<Integer>> iterbl) {
		List<List<Integer>> actual = new ArrayList<List<Integer>>();
		Integer level = null;
		List<Integer> levels = new ArrayList<Integer>();
		Iterator<NodeWithLevel<Integer>> i = iterbl.iterator();
		while(i.hasNext()) {
			NodeWithLevel<Integer> n = i.next();
			if (!Integer.valueOf(n.getLevel()).equals(level)) {
				level = n.getLevel();
				levels.add(level);
				actual.add(new ArrayList<Integer>());
			}
			actual.get(actual.size() - 1).add(n.getNode().getData());
		}
		Assert.assertEquals(Utils.createIntegerListUniform(0, levelCount-1, 1), levels);
		Assert.assertEquals(expected, actual);
	}
	
	private void exploreSiblings(Node<WithNextRight<Integer>> root, List<Integer> siblings) {
		Node<WithNextRight<Integer>> firstNode = root, iter;
		while(firstNode != null) {
			iter = firstNode;
			while(iter != null) {
				siblings.add(iter.getData().getData());
				iter = iter.getData().getNextRight();
			}
			firstNode = firstNode.getLeft();
		}
	}
	
	public static Integer[] array(Integer... arr) {
		return arr;
	}
	
	public void testMaxBinarySubtree() throws IOException {
//		{
//			BinaryTree<Integer> t = BinaryTreeUtils.fromTgf(new File("data/iview/trees/testMaxBstSubtree.tgf"));
//			Node<Integer> maxBst = BinaryTreeUtils.maxBstRooted(t.getRoot(), IntegerComparator.instance());
//			BinaryTree<Integer> expectedMaxBst = BinaryTreeUtils.fromTgf(new File("data/iview/trees/testMaxBstSubtree_Res.tgf"));
//			Assert.assertTrue(BinaryTreeUtils.isSame(IntegerComparator.instance(), maxBst, expectedMaxBst.getRoot()));
//		}
		
		{
			BinaryTree<Integer> t = BinaryTreeUtils.fromTgf(new File("data/iview/trees/testMaxBstSubtree2.tgf"));
			Node<Integer> maxBst = BinaryTreeUtils.maxBstRooted(t.getRoot(), IntegerComparator.instance());
			BinaryTree<Integer> expectedMaxBst = BinaryTreeUtils.fromTgf(new File("data/iview/trees/testMaxBstSubtree2_Res.tgf"));
			Assert.assertTrue(BinaryTreeUtils.isSame(IntegerComparator.instance(), maxBst, expectedMaxBst.getRoot()));
		}
		
		{
			BinaryTree<Integer> t = BinaryTreeUtils.fromTgf(new File("data/iview/trees/testMaxBstSubtree3.tgf"));
			Node<Integer> maxBst = BinaryTreeUtils.maxBstRooted(t.getRoot(), IntegerComparator.instance());
//			System.out.println(BinaryTreeUtils.writeAsTgfToFile(maxBst, "data/gen/iview/trees/trdlng.tgf").getAbsolutePath());
			BinaryTree<Integer> expectedMaxBst = BinaryTreeUtils.fromTgf(new File("data/iview/trees/testMaxBstSubtree3_Res.tgf"));
			Assert.assertTrue(BinaryTreeUtils.isSame(IntegerComparator.instance(), maxBst, expectedMaxBst.getRoot()));
		}
	}
	
	public void testSortedArrayToBalancedBST() throws IOException {
		{
			BinaryTree<Integer> t = BinaryTreeUtils.toBst(new int[]{});
			Assert.assertTrue(t.size() == 0);
		}
		
		{
			BinaryTree<Integer> t = BinaryTreeUtils.toBst(new int[]{1});
			BinaryTree<Integer> expected = BinaryTreeUtils.fromTgf(new File("data/iview/trees/testSortedArrayToBalancedBST1_Res.tgf"));
			Assert.assertTrue(BinaryTreeUtils.isSame(IntegerComparator.instance(), expected.getRoot(), t.getRoot()));
		}
		
		{
			BinaryTree<Integer> t = BinaryTreeUtils.toBst(new int[]{1, 3});
			BinaryTree<Integer> expected = BinaryTreeUtils.fromTgf(new File("data/iview/trees/testSortedArrayToBalancedBST2_Res.tgf"));
			Assert.assertTrue(BinaryTreeUtils.isSame(IntegerComparator.instance(), expected.getRoot(), t.getRoot()));
		}
		
		{
			BinaryTree<Integer> t = BinaryTreeUtils.toBst(new int[]{1, 2, 3});
			BinaryTree<Integer> expected = BinaryTreeUtils.fromTgf(new File("data/iview/trees/testSortedArrayToBalancedBST3_Res.tgf"));
			Assert.assertTrue(BinaryTreeUtils.isSame(IntegerComparator.instance(), expected.getRoot(), t.getRoot()));
		}
		
		{
			BinaryTree<Integer> t = BinaryTreeUtils.toBst(new int[]{1, 2, 3, 4});
			BinaryTree<Integer> expected = BinaryTreeUtils.fromTgf(new File("data/iview/trees/testSortedArrayToBalancedBST4_Res.tgf"));
			Assert.assertTrue(BinaryTreeUtils.isSame(IntegerComparator.instance(), expected.getRoot(), t.getRoot()));
		}
		
		{
			BinaryTree<Integer> t = BinaryTreeUtils.toBst(new int[]{1, 2, 3, 4, 5});
			BinaryTree<Integer> expected = BinaryTreeUtils.fromTgf(new File("data/iview/trees/testSortedArrayToBalancedBST5_Res.tgf"));
			Assert.assertTrue(BinaryTreeUtils.isSame(IntegerComparator.instance(), expected.getRoot(), t.getRoot()));
		}
		
		{
			BinaryTree<Integer> t = BinaryTreeUtils.toBst(Utils.createIntArray1D(7, 105*49, 7));
			BinaryTree<Integer> expected = BinaryTreeUtils.fromTgf(new File("data/iview/trees/testSortedArrayToBalancedBST6x_Res.tgf"));
			Assert.assertTrue(BinaryTreeUtils.isSame(IntegerComparator.instance(), expected.getRoot(), t.getRoot()));
//			System.out.println(BinaryTreeUtils.writeAsTgfToFile(t, "data/gen/iview/trees/testSortedArrayToBalancedBST6x_Res.tgf").getAbsolutePath());
		}
		
	}
	
	public void testSortedListToBalancedBST() throws IOException {
		{
			BinaryTree<Integer> t = BinaryTreeUtils.toBst(createSimpleList(new int[]{}));
			Assert.assertTrue(t.size() == 0);
		}
		
		{
			int[] arr = new int[]{1};
			BinaryTree<Integer> t = BinaryTreeUtils.toBst(createSimpleList(arr));
			testSortedListToBalancedBST(t, arr);
		}
		
		{
			int[] arr = new int[]{1, 3};
			BinaryTree<Integer> t = BinaryTreeUtils.toBst(createSimpleList(arr));
			testSortedListToBalancedBST(t, arr);
		}
		
		{
			int[] arr = new int[]{1, 2, 3};
			BinaryTree<Integer> t = BinaryTreeUtils.toBst(createSimpleList(arr));
			testSortedListToBalancedBST(t, arr);
		}
		
		{
			int[] arr = new int[]{1, 2, 3, 4};
			BinaryTree<Integer> t = BinaryTreeUtils.toBst(createSimpleList(arr));
			testSortedListToBalancedBST(t, arr);
		}
		
		{
			int[] arr = new int[]{1, 2, 3, 4, 5};
			BinaryTree<Integer> t = BinaryTreeUtils.toBst(createSimpleList(arr));
			testSortedListToBalancedBST(t, arr);
		}
		
		{
			int[] arr = Utils.createIntArray1D(1, 14, 1);
			BinaryTree<Integer> t = BinaryTreeUtils.toBst(createSimpleList(arr));
			testSortedListToBalancedBST(t, arr);
		}
		
		{
			for (int i = 6; i <= 1024; i++) {
				int[] arr = Utils.createIntArray1D(1, i, 1);
				BinaryTree<Integer> t = BinaryTreeUtils.toBst(createSimpleList(arr));
				testSortedListToBalancedBST(t, arr);
			}
		}
		
		{
			int[] arr = Utils.createIntArray1D(7, 105*49, 7);
			BinaryTree<Integer> t = BinaryTreeUtils.toBst(createSimpleList(arr));
			testSortedListToBalancedBST(t, arr);
		}
	}
	
	private void testSortedListToBalancedBST(BinaryTree<Integer> t, int[] arr) {
		Assert.assertTrue(BinaryTreeUtils.isBst(IntegerComparator.instance(),
				t.getRoot(), arr[0],
				arr[arr.length - 1])
				&& 
				BinaryTreeUtils.isBalanced(t.getRoot()));
		Assert.assertEquals(arr.length, t.size());
		
	}

	private static SingeLinkedList<Integer> createSimpleList(int[] elements ) {
		SingeLinkedList<Integer> l = new SingeLinkedList<Integer>();
		if (elements.length == 0) {
			return l; 
		}
		SingeLinkedList.Node<Integer> tail = l.add(elements[0]);
		for (int i = 1; i < elements.length; i++) {
			tail = SingeLinkedList.insertAfter(tail, elements[i]);
		}
		return l;
	}
	
	public void testToDoubleLinkedList() {
		testToDoubleLinkedList(new int[0]);
		testToDoubleLinkedList(new int[] {1});
		testToDoubleLinkedList(new int[] {1, 2});
		testToDoubleLinkedList(new int[] {1, 2, 4});
		testToDoubleLinkedList(new int[] {1, 2, 4, 8});
		testToDoubleLinkedList(new int[] {1, 2, 4, 8, 16});
		testToDoubleLinkedList(new int[] {1, 2, 4, 8, 16, 32});
		testToDoubleLinkedList(Utils.createIntArray1D(10, 10000, 10));
		testToDoubleLinkedList(Utils.createIntArray1D(7, 1071, 16));
	}

	private void testToDoubleLinkedList(int[] arr) {
		BinaryTree<Integer> t = BinaryTreeUtils.toBst(arr);
		
		Node<Integer> listPtr = BinaryTreeUtils.toDoubleLinkedList(t.getRoot());
		Node<Integer> prev = listPtr != null? listPtr.getLeft() : null;
		Node<Integer> firstPtr = listPtr; 
		
		int size = 0;
//		AdjGraph<Integer, Void> g = new AdjGraph<Integer, Void>(true, size);
		while(listPtr != null) {
			size++;
			Assert.assertEquals((Integer)arr[size - 1], listPtr.getData());
			Assert.assertEquals(prev, listPtr.getLeft());
			if (prev != null) {
				Assert.assertEquals(prev.getRight(), listPtr);
			}
			prev = listPtr;
			listPtr = listPtr.getRight();
			if (firstPtr == listPtr) { break; }
		}
		Assert.assertEquals(size, arr.length);
		if (firstPtr != null) {
			Assert.assertEquals(prev.getRight(), firstPtr);
			Assert.assertEquals(firstPtr.getLeft(), prev);
		}
//		try {
//			TgfGraphFactory.saveGraphAsTgf(g, new IConverter<Integer, String>() {
//				@Override
//				public String convert(Integer n) {
//					return ""+n;
//				}
//			},new IConverter<Void, String>() {
//
//				@Override
//				public String convert(Void data) {
//					return "";
//				}
//				
//			}, "data/gen/iview/trees/dll.tgf");
//		} catch (IOException e) {
//			e.printStackTrace();
//		}
	}
	
	public void testLowestCommonAncestorInBst() throws IOException {
		BinaryTree<Integer> t = BinaryTreeUtils.toBst(new int[]{1, 2, 4, 8, 16, 32, 64});
		testLowestCommonAncestorInBst(t, t.lookupNode(2), t.lookupNode(16), t.lookupNode(8));
		testLowestCommonAncestorInBst(t, t.lookupNode(8), t.lookupNode(8), t.lookupNode(8));
		testLowestCommonAncestorInBst(t, t.lookupNode(2), t.lookupNode(32), t.lookupNode(8));
		testLowestCommonAncestorInBst(t, t.lookupNode(4), t.lookupNode(16), t.lookupNode(8));
		testLowestCommonAncestorInBst(t, t.lookupNode(1), t.lookupNode(4), t.lookupNode(2));
		testLowestCommonAncestorInBst(t, t.lookupNode(16), t.lookupNode(64), t.lookupNode(32));
		
		t = BinaryTreeUtils.toBst(Utils.createIntArray1D(1, 127, 1));
		testLowestCommonAncestorInBst(t, t.lookupNode(49), t.lookupNode(65), t.lookupNode(64));
		testLowestCommonAncestorInBst(t, t.lookupNode(18), t.lookupNode(25), t.lookupNode(24));
		testLowestCommonAncestorInBst(t, t.lookupNode(33), t.lookupNode(48), t.lookupNode(48));
		Node<Integer> n2 = t.lookupNode(2);
		t.insert(2);
		Node<Integer> n1 = t.insert(2);
		t.insert(2);
		t.insert(1);
		t.insert(2);
		t.insert(2);
		t.insert(2);
		t.insert(1);
		testLowestCommonAncestorInBst(t, n1, t.lookupNode(12), t.lookupNode(8));
		testLowestCommonAncestorInBst(t, n1, t.lookupNode(12), t.lookupNode(8));
		testLowestCommonAncestorInBst(t, n1, t.lookupNode(4), t.lookupNode(4));
		testLowestCommonAncestorInBst(t, n1, n2, n2);
//		System.out.println(BinaryTreeUtils.writeAsTgfToFile(t, "data/gen/iview/trees/complete127.tgf").getAbsolutePath());
	}
	
	private void testLowestCommonAncestorInBst(BinaryTree<Integer> t, Node<Integer> n1, Node<Integer> n2, Node<Integer> expected) {
		Node<Integer> actual = BinaryTreeUtils.lowestCommonAncestorInBst(t.getRoot(), n1, n2);
		Assert.assertEquals(expected, actual);
	}
	
	public void testLowestCommonAncestor() throws IOException {
		BinaryTree<Integer> t = BinaryTreeUtils.toBst(new int[]{1, 2, 4, 8, 16, 32, 64});
//		System.out.println(BinaryTreeUtils.writeAsTgfToFile(t, "data/gen/iview/trees/complete127.tgf").getAbsolutePath());
		testLowestCommonAncestor(t, t.lookupNode(8), t.lookupNode(8), t.lookupNode(8));
		testLowestCommonAncestor(t, t.lookupNode(2), t.lookupNode(16), t.lookupNode(8));
		testLowestCommonAncestor(t, t.lookupNode(2), t.lookupNode(32), t.lookupNode(8));
		testLowestCommonAncestor(t, t.lookupNode(4), t.lookupNode(16), t.lookupNode(8));
		testLowestCommonAncestor(t, t.lookupNode(1), t.lookupNode(4), t.lookupNode(2));
		testLowestCommonAncestor(t, t.lookupNode(16), t.lookupNode(64), t.lookupNode(32));
		
		t = BinaryTreeUtils.toBst(Utils.createIntArray1D(1, 127, 1));
		testLowestCommonAncestor(t, t.lookupNode(49), t.lookupNode(65), t.lookupNode(64));
		testLowestCommonAncestor(t, t.lookupNode(18), t.lookupNode(25), t.lookupNode(24));
		testLowestCommonAncestor(t, t.lookupNode(33), t.lookupNode(48), t.lookupNode(48));
		Node<Integer> n2 = t.lookupNode(2);
		t.insert(2);
		Node<Integer> n1 = t.insert(2);
		t.insert(2);
		t.insert(1);
		t.insert(2);
		t.insert(2);
		t.insert(2);
		t.insert(1);
		testLowestCommonAncestor(t, n1, t.lookupNode(12), t.lookupNode(8));
		testLowestCommonAncestor(t, n1, t.lookupNode(12), t.lookupNode(8));
		testLowestCommonAncestor(t, n1, t.lookupNode(4), t.lookupNode(4));
		testLowestCommonAncestor(t, n1, n2, n2);
	}
	
	private void testLowestCommonAncestor(BinaryTree<Integer> t, Node<Integer> n1, Node<Integer> n2, Node<Integer> expected) {
		Node<Integer> actual = BinaryTreeUtils.lowestCommonAncestor(t.getRoot(), n1, n2);
		Assert.assertEquals(expected, actual);
	}
	
	public void testLowestCommonAncestorUsingParentUsingParent() throws IOException {
		BinaryTree<Integer> t = BinaryTreeUtils.toBst(new int[]{1, 2, 4, 8, 16, 32, 64});
		System.out.println(BinaryTreeUtils.writeAsTgfToFile(t, "data/gen/iview/trees/complete127.tgf").getAbsolutePath());
		testLowestCommonAncestorUsingParent(t, t.lookupNode(8), t.lookupNode(8), t.lookupNode(8));
		testLowestCommonAncestorUsingParent(t, t.lookupNode(2), t.lookupNode(16), t.lookupNode(8));
		testLowestCommonAncestorUsingParent(t, t.lookupNode(2), t.lookupNode(32), t.lookupNode(8));
		testLowestCommonAncestorUsingParent(t, t.lookupNode(4), t.lookupNode(16), t.lookupNode(8));
		testLowestCommonAncestorUsingParent(t, t.lookupNode(1), t.lookupNode(4), t.lookupNode(2));
		testLowestCommonAncestorUsingParent(t, t.lookupNode(16), t.lookupNode(64), t.lookupNode(32));
		
		t = BinaryTreeUtils.toBst(Utils.createIntArray1D(1, 127, 1));
		testLowestCommonAncestorUsingParent(t, t.lookupNode(49), t.lookupNode(65), t.lookupNode(64));
		testLowestCommonAncestorUsingParent(t, t.lookupNode(18), t.lookupNode(25), t.lookupNode(24));
		testLowestCommonAncestorUsingParent(t, t.lookupNode(33), t.lookupNode(48), t.lookupNode(48));
		Node<Integer> n2 = t.lookupNode(2);
		t.insert(2);
		Node<Integer> n1 = t.insert(2);
		t.insert(2);
		t.insert(1);
		t.insert(2);
		t.insert(2);
		t.insert(2);
		t.insert(1);
		testLowestCommonAncestorUsingParent(t, n1, t.lookupNode(12), t.lookupNode(8));
		testLowestCommonAncestorUsingParent(t, n1, t.lookupNode(12), t.lookupNode(8));
		testLowestCommonAncestorUsingParent(t, n1, t.lookupNode(4), t.lookupNode(4));
		testLowestCommonAncestorUsingParent(t, n1, n2, n2);
	}
	
	private void testLowestCommonAncestorUsingParent(BinaryTree<Integer> t, Node<Integer> n1, Node<Integer> n2, Node<Integer> expected) {
		Node<Integer> actual = BinaryTreeUtils.lowestCommonAncestorUsingParent(t.getRoot(), n1, n2);
		Assert.assertEquals(expected, actual);
	}
	
	public void testRabbit() throws IOException {
//		BinaryTree<Integer> t =  BinaryTreeUtils.createCompleteTree(4);
//		BinaryTree<Integer> t = createTree(IntegerComparator.instance(), 20, 107, 33, 38, 48, 70,
//				136, 112, 109, 130, 116, 245, 138, 228, 183, 201, 231, 233,
//				265, 295);
//		BinaryTree<Integer> t = createTree(IntegerComparator.instance(), 5, 1, 6, 4, 2, 3, 17, 11, 8, 9);
//		Integer level = null;
//		for (NodeWithLevel<Integer > n : BinaryTreeUtils.iterateLevelsZigzag(t.getRoot())) {
//			if (!Integer.valueOf(n.getLevel()).equals(level)) {
//				level = n.getLevel();
//				System.out.println();
//			}
//			System.out.print(n.getNode().getData()+ " ");
//		}
//		System.out.println();
//		BinaryTree<Integer> t = BinaryTreeUtils.fromTgf(new File("data/gen/iview/trees/test123456.tgf"));
//		System.out.println(BinaryTreeUtils.printBorders(t.getRoot()));
//		
//		BinaryTree<Integer> t = BinaryTreeUtils.fromTgf(new File("data/gen/iview/trees/testMaxBstSubtree.tgf"));
//		Node<Integer> maxBst = BinaryTreeUtils.maxBstWithRemovals(t.getRoot(), IntegerComparator.instance());
//		System.out.println(BinaryTreeUtils.writeAsTgfToFile(maxBst, "data/gen/iview/trees/testMaxBstSubtreeRemoval_Res.tgf").getAbsolutePath());
		
		
//		System.out.println(BinaryTreeUtils.printBorders(t.getRoot()));
//		System.out.println(BinaryTreeUtils.toString(t.getRoot()));
//		List<Integer> list = Arrays.asList(2,1,3,1);
//		Collections.sort(list);
//		List<Integer> reversedList = Utils.reversedList(list);
	}
}
